import java.util.*;

/**
 * @Author ZhangCuirong
 * @Date 2025/10/10 12:28
 * @description:
 */
public class Solution12 {
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder();
        Map<Integer, String> map = new TreeMap<>((o1, o2) -> o2-o1);
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");
        while (num != 0) {
            for (Integer key : map.keySet()) {
                while (num >= key) {
                    res.append(map.get(key));
                    num = num - key;
                }
            }
        }
        return res.toString();
    }
    public static void main(String[] args) {
        Solution12 solution = new Solution12();
        System.out.println(solution.intToRoman(3749));
        System.out.println(solution.intToRoman(58));
        System.out.println(solution.intToRoman(1994));
    }
}
